package Demo86;

import java.util.LinkedList;
import java.util.Queue;

/**
 *  被围绕的区域
 * https://leetcode.cn/problems/surrounded-regions/
 * 使用辅助vis的写法
 */
class Solution {
    boolean[][] vis;
    int m,n;
    char[][] board;
    int[] bx = new int[] {0,0,1,-1};
    int[] by = new int[] {1,-1,0,0};
    public void solve(char[][] board) {
        // 初始化准备
        this.board = board;
        m = board.length;
        n = board[0].length;
        vis = new boolean[m][n];

        // 遍历上边
        int i = 0;
        while(i == 0) {
            for(int j = 0; j < n;j++) {
                if(board[i][j] == 'O' && !vis[i][j]) {
                    bfs(i,j,false);
                }
            }
            i++;
        }
        // 遍历下边
        i = m-1;
        while(i == m-1) {
            for(int j = 0; j < n;j++) {
                if(board[i][j] == 'O' && !vis[i][j]) {
                    bfs(i,j,false);
                }
            }
            i++;
        }
        // 遍历左边
        int x = 0, y = 0;
        while(y == 0) {
            while(x < m - 1) {
                if(board[x][y] == 'O' && !vis[x][y]) {
                    bfs(x,y,false);
                }
                x++;
            }
            y++;
        }
        // 遍历右边
        x = 0; y = n - 1;
        while(y == n -1) {
//            System.out.println("==============");

            while(x < m) {
//                System.out.print("[" + x +","+ y+ "]  ");
//                System.out.print(board[x][y]);
                if(board[x][y] == 'O' && !vis[x][y]) {
                    bfs(x,y,false);
                }
                x++;
//                System.out.println();
            }
//            System.out.println("==============");
            y++;
        }

        for(int ix = 1; ix < m - 1; ix++) {
            for(int iy = 1; iy < n - 1; iy++) {
                if(board[ix][iy] == 'O' && !vis[ix][iy]) {
                    bfs(ix,iy,true);
                }
            }
        }
    }
    private void bfs(int i, int j, boolean tmp) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {i,j});
        vis[i][j] = true;
        if(tmp) {
            board[i][j] = 'X';
        }
        while(!q.isEmpty()) {
            int[] t = q.poll();
            int a = t[0], b = t[1];
            for(int k = 0; k < 4; k++) {
                int x = a + bx[k], y = b + by[k];
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O' && !vis[x][y]) {
                    q.add(new int[] {x,y});
                    vis[x][y] = true;
                    if(tmp) {
                        board[x][y] = 'X';
                    }
                }
            }
        }
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] board =  new char[][] {{'O','X','O','O','X','X'},{'O','X','X','X','O','X'},{'X','O','O','X','O','O'},{'X','O','X','X','X','X'},{'O','O','X','O','X','X'},{'X','X','O','O','O','O'}};
        for (char[] chs : board) {
            for(char ch : chs) {
                System.out.print(ch + " ");
            }
            System.out.println();
        }
        solution.solve(board);
        System.out.println("================================");
        for (char[] chs : board) {
            for(char ch : chs) {
                System.out.print(ch + " ");
            }
            System.out.println();
        }
    }
}